
package jleda.list;

import java.util.*;

public class LinkedListInt implements Iterable<Integer> {
	private Node root = new Node( 0, null, null );
	private int size = 0;
	
	public LinkedListInt() {
		root.next = root.prev = root;
	}
	
	public void add( int index, int data ) {
		Node t = root;
		
		if( index < (size >> 1) ) {
			for( int i = 0; i < index; i++ )
				t = t.next;
			
			t.next = t.next.prev = new Node( data, t, t.next );
		} else {
			for( int i = size; i > index; i-- )
				t = t.prev;
			
			t.prev = t.prev.next = new Node( data, t.prev, t );
		}
		
		size++;
	}
	
	public void addFirst( int data ) {
		root.next = root.next.prev = new Node( data, root, root.next );
		size++;
	}
	
	public void addLast( int data ) {
		root.prev = root.prev.next = new Node( data, root.prev, root );
		size++;
	}
	
	public int getFirst() {
		return root.next.data;
	}
	
	public int getLast() {
		return root.prev.data;
	}
	
	public int get( int index ) {
		Node t = root;
		
		if( index < (size >> 1) )
			for( int i = 0; i <= index; i++ )
				t = t.next;
		else
			for( int i = size; i > index; i-- )
				t = t.prev;
		
		return t.data;
	}
	
	public void set( int index, int data ) {
		Node t = root;
		
		if( index < (size >> 1) )
			for( int i = 0; i <= index; i++ )
				t = t.next;
		else
			for( int i = size; i > index; i-- )
				t = t.prev;
		
		t.data = data;
	}
	
	public void removeFirst() {
		root.next.next.prev = root;
		root.next = root.next.next;
		size--;
	}
	
	public void removeLast() {
		root.prev.prev.next = root;
		root.prev = root.prev.prev;
		size--;
	}
	
	public int remove( int index ) {
		Node t = root;
		
		if( index < (size >> 1) ) {
			for( int i = 0; i <= index; i++ )
				t = t.next;
			
			t.next.prev = t.prev;
			t.prev.next = t.next;
		} else {
			for( int i = size; i > index; i-- )
				t = t.prev;
			
			t.prev.next = t.next;
			t.next.prev = t.prev;
		}
		
		size--;
		return t.data;
	}
	
	public boolean removeElement( int data ) {
		Node t = root;
		
		while( ( t = t.next ) != root )
			if( t.data == data ) {
				t.prev.next = t.next;
				t.next.prev = t.prev;
				size--;
				return true;
			}
		
		return false;
	}
	
	public boolean removeAll( Collection<Integer> c ) {
		boolean flag = false;
		
		for( Integer data : c )
			if( removeElement( data ) ) {
				flag = true;
				while( removeElement( data ) );
			}
		
		return flag;
	}
	
	public void clear() {
		Node t = root.next;
		
		while( t != root ) {
			Node u = t.next;
			t.next = t.prev = null;
			t = u;
		}
		
		root.next = root.prev = root;
		size = 0;
	}
	
	public boolean contains( int data ) {
		Node t = root;
		
		while( ( t = t.next ) != root )
			if( t.data == data )
				return true;
		
		return false;
	}
	
	public boolean containsAll( Collection<Integer> c ) {
		for( Integer data : c ) {
			Node t = root;
			boolean flag = false;
			
			while( ( t = t.next ) != root )
				if( t.data == data ) {
					flag = true;
					break;
				}
			
			if( !flag )
				return false;
		}
		
		return true;
	}
	
	public int size() {
		return size;
	}
	
	public Iterator<Integer> iterator() {
		return new LLIterator();
	}
	
	public ListIterator<Integer> listIterator() {
		return new LLIterator();
	}
	
	public ListIterator<Integer> listIterator( int index ) {
		return new LLIterator( index );
	}
	
	public String toString() {
		if( root.next == root )
			return "[]";
		
		StringBuilder sb = new StringBuilder( "[" + Integer.toString( root.next.data ) );
		
		for( Node n = root.next.next; n != root; n = n.next )
			sb.append( ", " ).append( n.data );
		
		return sb.append( ']' ).toString();
	}
	
	private class Node {
		int data;
		Node prev, next;
		
		Node( int data, Node prev, Node next ) {
			this.data = data;
			this.prev = prev;
			this.next = next;
		}
	}
	
	private class LLIterator implements ListIterator<Integer> {
		Node next = root, lastReturned = root;
		int nextIndex = 0;
		
		LLIterator() {
			next = next.next;
		}
		
		LLIterator( int index ) {
			if( index < (size >> 1) )
				for( ; nextIndex <= index; nextIndex++ )
					next = next.next;
			else
				for( nextIndex = size; nextIndex > index; nextIndex-- )
					next = next.prev;
		}
		
		public Integer next() {
			nextIndex++;
			lastReturned = next;
			next = next.next;
			return next.prev.data;
		}
		
		public Integer previous() {
			nextIndex--;
			lastReturned = next = next.prev;
			return next.data;
		}
		
		public void add( Integer data ) {
			next.prev = next.prev.next = new Node( data, next.prev, next );
			nextIndex++;
			size++;
		}
		
		public void set( Integer data ) {
			lastReturned.data = data;
		}
		
		public void remove() {
			lastReturned.prev.next = lastReturned.next;
			lastReturned.next.prev = lastReturned.prev;
			
			if( lastReturned == next )
				next = next.next;
			else
				nextIndex--;
			
			size--;
		}
		
		public boolean hasNext() {
			return nextIndex != size;
		}
		
		public boolean hasPrevious() {
			return nextIndex != 0;
		}
		
		public int nextIndex() {
			return nextIndex;
		}
		
		public int previousIndex() {
			return nextIndex - 1;
		}
	}
}
